Catalan Numbers

释义 Definition

卡特兰数（Catalan numbers）是一列在组合数学中极其常见的整数序列，用来计数许多不同类型的结构，例如：正确匹配的括号串、二叉树的形状、将多边形三角剖分的方法数、不过对角线相交的路径数等。常用记号为 \(C_n\)，其中 \[ C_n=\frac{1}{n+1}\binom{2n}{n}\quad (n\ge 0). \] （该术语也可泛指由这列数所计数的“卡特兰类”对象。）

发音 Pronunciation (IPA)

/ˈkætəlæn ˈnʌmbərz/

例句 Examples

Catalan numbers count how many correct parentheses strings there are of length 2n.
卡特兰数用于计算长度为 2n 的正确括号串有多少种。

In combinatorics, the nth Catalan number can be written as \(C_n=\frac{1}{n+1}\binom{2n}{n}\), which also equals the number of full binary trees with n internal nodes.
在组合数学中，第 n 个卡特兰数可写为 \(C_n=\frac{1}{n+1}\binom{2n}{n}\)，它也等于具有 n 个内部结点的满二叉树的数量。

词源 Etymology

“Catalan numbers”得名于比利时数学家欧仁·夏尔·卡特兰（Eugène Charles Catalan）。该序列在19世纪的组合计数研究中被系统讨论，后来因其在各种计数问题中反复出现而广为人知。

相关词 Related Words

• Combinatorics
• Binomial Coefficient
• Recurrence
• Generating Function
• Binary Tree
• Dyck Path
• Parentheses
• Triangulation

文学与著作中的出现 Literary Works

• **Concrete Mathematics**（Graham, Knuth, Patashnik）：在递推、计数与生成函数相关章节中讨论卡特兰数及其应用。
• **Enumerative Combinatorics, Volume 2**（Richard P. Stanley）：在枚举组合的经典主题中多处出现卡特兰数与其变体。
• **A=B**（Marko Petkovšek, Herbert Wilf, Doron Zeilberger）：在超几何恒等式与组合恒等式的语境下涉及卡特兰型数列。